#include<iostream>

using namespace std;
const int N=1e5+10;

//双数组静态实现
int e[N], ne[N], h=0, id=0;
int mp[N]; // mp[i] 表示 i 这个数存储的位置

void  Push_front(int x)//头插
{
	id++;
	e[id]=x;

	mp[x]=id;//标记存储位置
	// 先让新结点指向头结点的下一个位置
    // 然后让头结点指向新来的结点
	ne[id]=ne[h];
	ne[h]=id;
}
void Print()
{
	for(int i=ne[h];i;i=ne[i])
	{
		cout<<e[i]<<" ";
	}
	cout<<endl;
}
// 按值查找
int find(int x)
{
    // // 解法一：遍历链表
    // for(int i = ne[h]; i; i = ne[i])
    // {
    //     if(e[i] == x) return i;
    // }
    // return 0;

    // 解法二：用 mp 数组优化,前提数组没有重复内容
    return mp[x];
}
// 在任意位置 p 之后，插入一个新的元素 x
void insert(int p, int x)
{
    id++;
    e[id] = x;
    mp[x] = id;

    ne[id] = ne[p];
    ne[p] = id;
}
// 删除任意位置 p 后面的元素
void erase(int p)
{
    if(ne[p]) // 当 p 不是最后一个元素的时候
    {
        mp[e[ne[p]]] = 0; // 把标记清空

        ne[p] = ne[ne[p]];
    }
}
int main()
{
	for(int i = 1; i <= 5; i++)
    {
        Push_front(i);
        Print();
    }
    cout<<find(3)<<endl;
    cout<<find(2)<<endl;
    insert(2,10);
    Print();
    cout<<find(10)<<endl;
	return 0;
}